package recursion;

/**
 * @author Liaorun
 */
public class LetASorted {

    public static void main(String[] args) {
        System.out.println(canSorted(new int[]{1, 2, 1}, new int[]{2, 0, 1}));
    }

    public static boolean canSorted(int[] A, int[] B) {
        return process(A, B, 0, Integer.MIN_VALUE);
    }

    /**
     * 已经遍历的部分是：A[0...index-1]，能保证遍历的部分已经有序了
     *
     * @param A
     * @param B
     * @param index
     * @param pre
     * @return
     */
    public static boolean process(int[] A, int[] B, int index, int pre) {
        if (index == A.length) {
            return true;
        }

        // index 还没到终止位置
        // 决策1，不交换如果能保证升序，就递归到下一个位置
        boolean p1 = pre > A[index] ? false : (process(A, B, index + 1, A[index]));
        // 决策2，交换如果能保证升序，就递归到下一个位置
        boolean p2 = pre > B[index] ? false : (process(A, B, index + 1, B[index]));

        return p1 | p2;
    }
}
